package MaximumsSumSubsequence;

import java.util.Random;

public class Main {

    static int f(int[] nums) {
        return f1(nums, 0, 0);
    }

    /**
     * @param nums
     * @param i    现在到了数组的第i个位置
     * @param sum  目前0~i的位置的和
     * @return
     */
    static int f1(int[] nums, int i, int sum) {
        if (i == nums.length) {
            return sum % 7 == 0 ? sum : 0;
        }
        return Math.max(f1(nums, i + 1, sum), f1(nums, i + 1, sum + nums[i]));
    }

    static int[] randArr(int max, int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * n) + 1;
        }
        return arr;
    }

    static int f2(int[] nums) {
        int n = nums.length;
        //dp[i][j]：在前i个数中一定存在子序列使得%7==j
        int[][] dp = new int[n+1][7];
        //-1表示不存在
        for(int i = 1; i < 7; i++) {
            dp[0][i] = -1;
        }
        int cur;
        int x;
        for (int i = 1; i <= n; i++) {
            x = nums[i-1];
            cur = nums[i-1]%7;

            for (int j = 0; j < 7; j++) {
                dp[i][j] = dp[i-1][j];
                int need = cur<=j?(j-cur):(j+7-cur);
                if(dp[i-1][need]!=-1) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][need] + x);
                }
            }
        }
        return dp[n][0];
    }



    public static void main(String[] args) {
        //测试次数
        int testTimes = 500;
        //数字范围是1~100
        int max = 100;
        //数组大小的范围：1~20
        int n = 20;
        for (int i = 0; i < testTimes; i++) {
            int len = (int) (Math.random() * n) + 1;
            int[] res = randArr(max, len);
            if(f(res)!=f2(res)) {
                System.out.println(res);
                break;
            }else {
                System.out.println("成功第"+(i+1)+"次");
            }
        }
    }

}
